import java.util.Arrays;

public class Solution1130 {
    public int mctFromLeafValues(int[] arr) {
        int[][] f=new int[arr.length][arr.length];
        for (int i=0;i<arr.length;i++){
            f[i][i]=arr[i];
        }
        for (int i=arr.length-1;i>=0;i--){
            for (int j=i+1;j<arr.length;j++){
                f[i][j]=Integer.MAX_VALUE;
                for (int k=i;k<j;k++){
                    f[i][j]=Math.min(f[i][j],f[i][k]+f[k+1][j]+max(arr,i,k)*max(arr,k+1,j));
                }
            }
        }
        return f[0][arr.length-1]- Arrays.stream(arr).sum();
    }

    private int max(int[] arr, int i, int j) {
        int ans=arr[i];
        for (int k=i+1;k<=j;k++){
            if (arr[k]>ans){
                ans=arr[k];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1130().mctFromLeafValues(new int[]{6,2,4}));
    }
}
